Conventional communication systems, including networks, include two or more interconnected nodes wherein each node functions as a junction point within the system. Information is transferred between nodes using electric, light, and/or radio waves, and typically involves transferring one or more codewords. Each codeword represents a symbol in a symbol set, such as an alphabet, and includes data for use by, and/or instructions for, a receiving node. Each codeword is defined by one or more binary digits, or bits.
Communication systems have limited bandwidth. In other words, there exists an upper limit, or maximum number, of bits which may be transferred per unit time. Contrary to this limitation is the need of many communication systems to transfer large quantities of symbols. This is particularly true in video applications, such as videophone and direct television, where video symbols typically represent chrominance and/or luminance values for picture elements ("pixels"), motion information, instructions indicating the content of the chrominance, and luminance values or marker codes. Marker codes are sync codes.
Data compression techniques have been incorporated into many communication systems to increase the number of codewords transferred given the available bandwidth. These techniques eliminate unnecessary data, redundancies, and the like from transmissions. Huffman Coding is one popular approach which is commonly used for video, audio/speech and high-speed data compression. Huffman Codes use variable length symbols wherein each symbol's length depends upon the probability of occurrence of the one or more codewords defining it.
Assume for example a symbol set of {bear, dart, wear, beet}. Each of the codewords used to represent the symbol set has a length inversely proportional to its symbol's usage. Assuming this symbol set is used in the English language, "wear" is likely to be said more often than "bear", more often than "dart", and more often than "beet". The coding may accordingly be {be, dar, w, beet}, where codeword length is equivalent to the number of letters. In point of fact, the English language presents another good example of variable length codewords wherein common words such as {it, in, a, car, the, if, I, a, an} are shorter than words used less frequently, such as {approximately, university, automobile, individually, myself, particularly}.
Source entropy is an optimal "loss-less" coding rate, in other words, the smallest average number of bits per symbol required to represent a particular symbol set or alphabet. Huffman Coding techniques have been found to reduce coding rates to nearly source entropy. In many conventional applications, such as video processing, however, the probability of all occurrences of the various symbols tends to change as the video image changes. This causes the current Huffman Codes to be an inefficient representation of the symbols. Worse, these changes typically occur at random.
The Huffman Codes accordingly cease to reduce coding rates to source entropy and require recalculation. This is often computationally difficult as the codeword for any one symbol depends on the probability of occurrence of the symbols in the alphabet. For large alphabets therefore each codeword, of which there are typically many, requires substantial computation.
One conventional solution periodically recalculates the Huffman Codes. Another solution determines the source entropy, and then estimates from that determination the coding rate for recalculating the Huffman Codes. Each approach is typically inaccurate, and in many situations demands substantially the same processing resource requirements needed to recalculate the Huffman Codes as when originally defined. The inability of conventional communication systems to generate, and regenerate, Huffman Codes to maintain substantially source entropy remains a dominant obstacle to producing high quality video, audio/speech and high-speed communication.